nLab abstract rewriting system

Idea

The notion of abstract rewriting system is the simplest mathematical formalization of what is a rewriting system. It doesn’t presuppose anything on the nature of the syntactical objects which are rewritten, thus the word “abstract”.

Definition

An abstract rewriting system $(X, \rightarrow)$ is given by a set $X$ and a binary relation $\rightarrow$ on $X$, ie. a subset of the cartesian product $X \times X$.

So this is a concept with an attitude: While an abstract re-writing system is just a relation, calling this relation an abstract rewriting system indicates that one is interested in studying the behaviour of chains of related elements $x \to x_1 \to x_2 \to \cdots$ (thought of as successive stages of rewriting $x$), for instance to see if they are confluent.

Related entries

• rewriting system

References

• Wikipedia, Abstract rewriting system

• Wikipedia, Confluence_(abstract_rewriting)